hemisus
Profile
Projects
Audio
Computer Network
Computer Vision
CS231n (2025)
Data Structure
Deep Learning
Linear Algebra
Machine Learning
Python
PyTorch
Reinforcement Learning
Home
Contact
Copyright © 2026 | Hemisus
Home
> Reinforcement Learning
Now Loading ...
Reinforcement Learning
[RL] 2. DP: Policy Iteration, Value Iteration
참고한 자료 파이썬과 케라스로 배우는 강화학습 (개정판) Github 이전 글에서 순차적 행동 결정 문제를 MDP로 정의하고, 벨만 기대 방정식과 최적 방정식을 얻었다. 이제 이 방정식을 풀 차례이다. 벨만 방정식을 푼다는 것은 방정식을 만족하는 가치함수를 찾는 것이다. 벨만 기대 방정식을 풀면 주어진 정책 $\pi$의 가치함수 $v_\pi$를 얻고, 벨만 최적 방정식을 풀면 최적 가치함수 \(v_*\)와 최적 큐함수 \(q_*\)를 얻는다. 에이전트는 정책에 따라 각 상태에서 어떤 행동을 할지 결정한다. 따라서 최종 목표는 가치함수 자체를 구하는 것이 아니라, 기대 반환값을 최대로 만드는 최적 정책 $\pi_*$를 찾는 것이다. 최적 큐함수를 알고 있다면, 각 상태에서 큐함수가 가장 큰 행동을 고르기만 하면 최적 정책을 얻을 수 있다. \[\pi_*(s) = \arg\max_{a \in A} q_*(s, a)\] 1. Dynamic Programming 다이내믹 프로그래밍(DP)은 큰 문제를 한 번에 풀지 않는다. 대신 문제를 작은 문제로 나누어 풀고, 그 해를 이용해 큰 문제의 해에 도달한다. MDP에서는 벨만 방정식을 통해 이러한 분할이 가능하다. 현재 상태의 가치가 다음 상태의 가치로 재귀적으로 표현되므로, 다음 상태들의 가치를 이용해 현재 상태의 가치를 계산할 수 있다. 따라서 DP에서는 가치함수를 한 번에 정확히 구하지 않는다. 임의의 초기값 $v_0$에서 시작하여, 벨만 방정식을 이용해 가치함수를 반복적으로 업데이트한다. \[v_0 \rightarrow v_1 \rightarrow v_2 \rightarrow \cdots \rightarrow v_k \rightarrow \cdots \rightarrow v_\pi\] DP로 벨만 방정식을 푸는 방법은 두 가지이다. 벨만 기대 방정식을 이용하는 정책 이터레이션(Policy Iteration)과, 벨만 최적 방정식을 이용하는 가치 이터레이션(Value Iteration)이다. DP를 적용할때 유의할 점은, 환경의 모델, 즉 상태 변환 확률 $P_{ss’}^a$과 보상함수 $R_s^a$를 알고 있어야 한다는 것이다. 벨만 방정식의 기댓값을 계산하려면 다음 상태가 어떤 확률로 나타나는지 알아야 하기 때문이다. 따라서 DP는 환경과 상호작용하며 배우는 학습(learning)이라기보다, 알려진 모델을 바탕으로 계산하는 계획(planning)에 가깝다. 책에서는 그리드월드 예제를 통해 내용을 설명한다. 그리드월드에서 에이전트는 격자 위를 상하좌우로 이동하며 장애물을 피해 목표 지점에 도달해야 한다. 2. Policy Iteration (정책 이터레이션) 정책 이터레이션은 임의의 정책에서 시작한다. 책에서는 모든 행동을 같은 확률로 선택하는 무작위 정책을 초기 정책으로 사용한다. 무작위 정책은 당연히 최적 정책이 아니므로, 현재 정책이 얼마나 좋은지 평가하고, 그 평가를 바탕으로 더 나은 정책으로 발전시켜야 한다. 이 두 과정을 반복하면 정책은 점점 개선되어 최적 정책에 수렴한다. \[\pi_0 \xrightarrow{\text{평가}} v_{\pi_0} \xrightarrow{\text{발전}} \pi_1 \xrightarrow{\text{평가}} v_{\pi_1} \xrightarrow{\text{발전}} \cdots \rightarrow \pi_*\] 정책 평가 (Policy Evaluation) 정책이 얼마나 좋은지를 판단하는 기준으로 가치함수를 사용할 수 있다. \[v_\pi(s) = \mathbb{E}_\pi\left[R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + \cdots \mid S_t = s\right]\] 가치함수는 상태 $s$에서 정책 $\pi$를 따라 행동했을 때 앞으로 받을 보상의 할인된 합(반환값)의 기댓값이다. 같은 상태에서 출발하더라도 어떤 정책을 따르느냐에 따라 받게 될 보상이 달라지므로, 가치함수는 그 자체로 정책의 좋고 나쁨을 판단하는 기준이 된다. 정책 이터레이션에서는 이 가치함수를 DP로 계산하기 위해 벨만 기대 방정식을 사용한다. \[v_\pi(s) = \mathbb{E}_\pi\left[R_{t+1} + \gamma v_\pi(S_{t+1}) \mid S_t = s\right]\] 이 식의 핵심은 미래의 모든 보상을 직접 더하지 않는다는 것이다. 대신 현재 상태에서 행동했을 때 받는 보상과 그 행동으로 도달할 수 있는 다음 상태들의 가치함수만으로 현재 상태의 가치함수를 표현한다. 기댓값 $\mathbb{E}_\pi$를 풀어 쓰면, 다음과 같이 계산 가능한 형태가 된다. \[v_\pi(s) = \sum_{a \in A} \pi(a \mid s) \left( R_s^a + \gamma \sum_{s' \in S} P_{ss'}^a \, v_\pi(s') \right)\] 각 행동을 선택할 확률 $\pi(a \mid s)$로, 그 행동을 했을 때의 보상과 다음 상태 가치의 합을 가중평균한 형태이다. 그런데 우리는 아직 참 가치함수 $v_\pi$를 모른다. 따라서 위 식의 우변에 참값 대신 현재까지 계산한 $k$번째 가치함수 $v_k$를 넣고, 그 결과를 $k+1$번째 가치함수 $v_{k+1}$로 삼는다. \[v_{k+1}(s) = \sum_{a \in A} \pi(a \mid s) \left( R_s^a + \gamma \sum_{s' \in S} P_{ss'}^a \, v_k(s') \right)\] $v_k$는 참값이 아니므로 한 번 계산한 $v_{k+1}$ 역시 참값이 아니다. 하지만 이 업데이트를 모든 상태에 대해 반복하면, 실제 보상 $R_s^a$에 대한 정보가 매 반복마다 주변 상태로 전파되면서 $v_k$는 $v_\pi$에 수렴한다. 위 수식은 모든 상태의 $v_{k+1}$을 이전 반복의 값 $v_k$만으로 계산하는 동기식 업데이트를 나타낸다. 이를 위해 $v_k$와 $v_{k+1}$을 저장할 테이블을 따로 두며, 책의 코드도 이 방식을 따른다. 반면 테이블을 하나만 두고 계산 즉시 값을 덮어쓰는 제자리 업데이트(in-place update)에서는 이웃 상태 중 일부는 이미 갱신된 $v_{k+1}$, 일부는 $v_k$를 참조하게 된다. 이 경우에도 모든 상태가 반복적으로 갱신되기만 하면 $v_\pi$로 수렴하며, 최신 값을 바로 활용하므로 보통 더 빠르게 수렴한다. 그리드월드는 어떤 상태에서 행동 $a$를 하면 항상 정해진 다음 상태 $s’$로 이동한다고 가정한다. 즉 상태 변환 확률이 해당 $s’$에 대해서만 1이고 나머지는 0이므로, $s’$에 대한 합이 사라져 식이 다음과 같이 단순해진다. \[v_{k+1}(s) = \sum_{a \in A} \pi(a \mid s) \left( R_s^a + \gamma \, v_k(s') \right)\] 이것이 한 번의 정책평가 과정이다. 한 번의 정책평가로는 제대로 정책이 평가될 수 없으므로 여러 번 반복한다. 정책 발전 (Policy Improvement) 정책 평가로 현재 정책의 가치함수를 구했다면, 이제 이를 바탕으로 정책을 발전시킬 차례이다. 정책을 발전시키는 방법은 여러 가지가 있지만, 책에서는 기본적인 방법인 탐욕 정책 발전(greedy policy improvement)을 사용한다. 정책은 각 상태에서 어떤 행동을 할지 정하는 것이다. 그런데 가치함수 $v_\pi(s)$는 상태 하나의 가치만 알려 줄 뿐, 그 상태에서 어떤 행동이 더 좋은지는 직접 알려 주지 않는다. 행동을 비교하려면 상태와 행동의 쌍에 대한 가치, 즉 큐함수가 필요하다. \[q_\pi(s, a) = \mathbb{E}_\pi\left[R_{t+1} + \gamma\, v_\pi(S_{t+1}) \mid S_t = s, A_t = a\right]\] 큐함수는 상태 $s$에서 행동 $a$를 한 뒤, 그 이후로는 정책 $\pi$를 따랐을 때의 기대 반환값이다. 기댓값을 풀어 쓰면 다음과 같이 계산 가능한 형태가 된다. \[q_\pi(s, a) = R_s^a + \gamma \sum_{s' \in S} P_{ss'}^a \, v_\pi(s')\] 이 식에서 알 수 있듯이, 큐함수는 정책 평가에서 구한 가치함수만으로 계산할 수 있다. 따라서 큐함수를 별도로 저장할 필요가 없다. 그리드월드처럼 행동에 따라 다음 상태가 하나로 정해지는 환경에서는 식이 더 단순해진다. \[q_\pi(s, a) = R_s^a + \gamma\, v_\pi(s')\] 탐욕 정책 발전은 상태 $s$에서 선택 가능한 모든 행동의 큐함수를 비교하고, 그중 큐함수가 가장 큰 행동을 선택한다. 이렇게 발전된 정책 $\pi’$는 다음과 같다. \[\pi'(s) = \arg\max_{a \in A} q_\pi(s, a)\] 큐함수가 최대인 행동이 여러 개라면, 그 행동들에 확률을 균등하게 나누어 준다. 예를 들어 두 행동의 큐함수가 같은 최댓값을 가지면 각각 $0.5$의 확률로, 세 행동이면 각각 $\frac{1}{3}$의 확률로 정책을 수정한다. 탐욕 정책 발전으로 얻은 정책은 이전 정책보다 나빠지지 않는다. 즉 모든 상태 $s$에 대해 다음이 성립한다. \[v_{\pi'}(s) \geq v_\pi(s)\] 정책 평가와 정책 발전을 반복하다가 정책이 더 이상 바뀌지 않는 순간이 온다. 이때는 각 상태에서 고르는 행동이 이미 큐함수를 최대로 만드는 행동이라는 뜻이다. 즉 이 시점의 가치함수는 벨만 최적 방정식을 만족하고, 그때의 정책이 최적 정책 $\pi_*$이다. 또한 유한 MDP에서는 정책의 개수가 유한하므로, 이 과정은 유한 번의 반복 안에 끝난다. 3. Value Iteration (가치 이터레이션) 정책 이터레이션에서는 정책과 가치함수가 명확히 분리되어 있었다. 정책 $\pi$는 별도로 저장되어 있고, 가치함수는 그 정책이 얼마나 좋은지를 평가하는 도구로만 쓰였다. 정책 평가를 아무리 반복해도 정책은 바뀌지 않으며, 정책은 정책 발전 단계에서만 바뀐다. 가치 이터레이션은 정책을 따로 두지 않는다. 대신 현재의 가치함수가 최적 가치함수라고 가정한다. 이 가정 하에, 최적 정책은 각 상태에서 큐함수가 가장 큰 행동을 고르는 것이므로 가치함수로부터 바로 얻을 수 있다. \[\pi(s) = \arg\max_{a \in A} \left( R_s^a + \gamma\, v_k(s') \right)\] 이 정책은 가장 좋은 행동 하나만을 선택하는 결정적(deterministic) 정책이다. 무작위 정책처럼 확률적으로 행동을 고르는 정책 이터레이션의 초기 정책과 대비된다. 이 결정적 정책을 벨만 기대 방정식에 대입하면, 행동에 대한 가중평균이 최댓값 하나로 바뀌어 결국 벨만 최적 방정식을 이용한 업데이트가 된다. 물론 처음의 가치함수는 최적이 아니므로 이 가정은 사실이 아니다. 하지만 업데이트를 반복하면 가치함수는 최적 가치함수에 수렴하고 최적 정책을 구할 수 있다. 따라서 가치 이터레이션은 정책을 따로 발전시키는 단계 없이 가치함수만 반복해서 업데이트하고, 정책은 수렴한 가치함수로부터 마지막에 한 번 꺼내 쓰면 된다. 가치함수 안에 정책이 내재적으로 포함되어 있다는 것이다. 벨만 최적 방정식은 다음과 같다. \[v_*(s) = \max_{a \in A} \mathbb{E}\left[R_{t+1} + \gamma\, v_*(S_{t+1}) \mid S_t = s, A_t = a\right]\] 벨만 기대 방정식과 비교하면, 정책 $\pi$에 대한 기댓값 $\mathbb{E}_\pi$ 대신 행동에 대한 최댓값 $\max_a$가 들어가 있다. 기댓값을 풀어 쓰면 다음과 같이 계산 가능한 형태가 된다. \[v_*(s) = \max_{a \in A} \left( R_s^a + \gamma \sum_{s' \in S} P_{ss'}^a \, v_*(s') \right)\] 정책 평가에서와 마찬가지로, 우리는 아직 참값 $v_*$를 모른다. 따라서 우변에 현재까지 계산한 $v_k$를 넣고, 그 결과를 $v_{k+1}$로 삼아 반복한다. \[v_{k+1}(s) = \max_{a \in A} \left( R_s^a + \gamma \sum_{s' \in S} P_{ss'}^a \, v_k(s') \right)\] 그리드월드에서는 행동에 따라 다음 상태가 하나로 정해지므로, $s’$에 대한 합이 사라져 다음과 같이 단순해진다. \[v_{k+1}(s) = \max_{a \in A} \left( R_s^a + \gamma\, v_k(s') \right)\] 정책 평가의 업데이트 식과 나란히 놓으면 차이가 분명해진다. \[\begin{aligned} \text{정책 이터레이션 (평가)} &: \quad v_{k+1}(s) = \sum_{a \in A} \pi(a \mid s) \left( R_s^a + \gamma\, v_k(s') \right) \\ \text{가치 이터레이션} &: \quad v_{k+1}(s) = \max_{a \in A} \left( R_s^a + \gamma\, v_k(s') \right) \end{aligned}\] 정책 평가는 정책이 정한 확률로 각 행동의 값을 가중평균하는 반면, 가치 이터레이션은 그중 최댓값만 취한다. 업데이트 식 자체에 “가장 좋은 행동을 고른다”는 정책 발전이 이미 포함되어 있는 셈이다. 이 업데이트를 모든 상태에 대해 반복하면 $v_k$는 $v_*$에 수렴한다. 이렇게 얻은 가치함수로부터, 앞서 본 $\arg\max$ 식으로 각 상태의 최적 행동을 꺼내면 최적 정책이 된다. \[\pi_*(s) = \arg\max_{a \in A} \left( R_s^a + \gamma\, v_*(s') \right)\] 정책 이터레이션 가치 이터레이션 사용하는 방정식 벨만 기대 방정식 벨만 최적 방정식 정책 저장 명시적으로 저장 저장하지 않음 (가치함수에 내재) 반복 단위 정책 평가 + 정책 발전 가치함수 업데이트 업데이트 연산 정책에 따른 가중평균 최댓값 정책을 얻는 시점 매 정책 발전마다 가치함수 수렴 후 $\arg\max$로 추출
Reinforcement Learning
· 2026-10-30
[RL] 1. MDP & Bellman Equation
참고한 자료 파이썬과 케라스로 배우는 강화학습 (개정판) Github 1. Reinforcement Learning? 강화학습은 머신러닝의 한 분야로, 지도학습과 비지도학습과는 다르게 정답이나 데이터에 대해 학습하는 것이 아닌, 주어진 환경에서 에이전트(Agent)의 행동에 따른 “보상”을 통해 학습하는 머신러닝 기법이다. 에이전트가 환경에서 어떤 행동을 하면 보상이 주어지는데, 이 보상을 최대화 하는 방법을 시행착오를 겪으며 학습하는 것이다. 이러한 강화학습은 단순히 한 시점에서 단번의 결정으로 해결되는 문제가 아닌, 여러 차례에 순차적인 결정을 요구하는 문제에 적용된다. 이러한 순차적 행동 결정 문제를 정의하는데 MDP(Markov Decision Process)를 사용한다. 2. MDP(Markov Decision Process) MDP는 순차적 행동 결정 문제를 정의하는 프레임워크로, 크게 다섯 가지 요소로 구성된다. \[\text{MDP} = \langle S,\ A,\ R,\ P,\ \gamma \rangle\] 상태 집합 $S$ 행동 집합 $A$ 보상 함수 $R$ 상태 변환 확률 $P$ 할인율 $\gamma$ 상태 (State) \[S_t = s\] 상태는 에이전트가 관찰할 수 있는 자신의 상황이다. 환경이 그리드월드일 때 에이전트가 있는 좌표 $(x, y)$ 가 상태가 되고, 전체가 5×5라면 상태 집합은 다음과 같다. \[S = \{(1,1), (1,2), \dots, (5,5)\}\] 주의할 점은 $S_t$ 가 확률변수라는 것이다. “시간 $t$ 에 에이전트가 어떤 상태에 있을지”는 그 전까지의 행동과 환경에 따라 달라지므로 고정된 값이 아니다. 그래서 “시간 $t$ 에 에이전트가 상태 $s$ 에 있다”는 사실은 $S_t = s$ 라고 표현한다. 행동 (Action) \[A_t = a\] 행동은 에이전트가 어떤 상태에서 취할 수 있는 선택지다. 그리드월드의 경우에는 상하좌우 네 가지다. \[A = \{\text{up},\ \text{down},\ \text{left},\ \text{right}\}\] 보상 함수 (Reward Function) \[r(s, a) = E[R_{t+1} \mid S_t = s,\ A_t = a]\] 보상은 환경이 에이전트에게 주는 유일한 학습할 수 있는 정보이다. 강화학습의 목표는 시간에 따라 얻는 보상의 합을 최대로 하는 행동을 에이전트가 선택하도록 만드는 것이다. 보상함수는 시간 $t$ 일 때 상태 $S_t = s$ 에서 $A_t = a$ 행동을 했을 경우 받을 보상에 대한 기댓값 $E[\cdot]$ 이다. 보상을 계산하는 주체는 환경인데, 환경에 따라서 같은 상태에 같은 행동을 해도 다른 보상을 줄 수 있기 때문에 확률적인 환경도 표현할 수 있도록 기댓값으로 정의한다. 또한 상태와 행동은 $S_t,\ A_t$ 인 반면 보상은 $R_{t+1}$ 이다. 에이전트는 시간 $t$ 에 행동을 결정하고, 그 행동에 대한 보상은 환경으로부터 다음 시점에 전달받는다. 즉 에이전트 입장에서 보상은 “행동한 뒤에 환경으로부터 받는 것”이므로 $t+1$ 인 시점에서 에이전트가 받는 보상을 $R_{t+1}$ 으로 표현한다. 보상은 에이전트가 알고 있는 것이 아닌, 환경이 알려주는 것이다. 상태 변환 확률 (State Transition Probability) \[P_{ss'}^a = P[S_{t+1} = s' \mid S_t = s,\ A_t = a]\] 상태 $s$ 에서 행동 $a$ 를 했을 때 다음 상태가 $s’$ 이 될 확률이다. 어떤 행동을 하였더라도 의도한대로 원하는 상태에 도달하지 못할 수도 있다. 미끄러지는 로봇, 바람이 불어 밀리는 등 상태의 변화는 환경의 불확실성, 확률적인 요인을 포함하고 있다. 이 확률 또한 에이전트는 알지 못하는 값으로, 환경의 모델(model)이라고도 부른다. 할인율 (Discount Factor) \[\gamma \in [0, 1]\] 동일한 보상일지라도 미래에 받게 될 보상은 당장 현재 받는 보상에 비해 가치가 떨어진다. 할인율은 미래의 가치를 현재의 가치로 할인하는 비율로, 시간 $t$로부터 $k$가 지난 뒤에 받을 보상이 $R_{t+k}$라고 하면, 이것의 현재 가치는 $\gamma^{k-1} R_{t+k}$ 이다. \[\gamma^{k-1} R_{t+k}\] 3. 정책 (Policy) MDP가 문제를 정의했다면, 정책은 에이전트가 문제의 모든 상태에서 취할 행동 양식이다. \[\pi(a \mid s) = P[A_t = a \mid S_t = s]\] 각 상태에서 어떤 행동을 할 확률인지를 나타내는 함수다. 그리드월드의 어떤 칸에서 정책이 $\pi(\text{up} \mid s) = 0.7,\ \pi(\text{right} \mid s) = 0.3$ 이라면, 그 칸에서는 70% 확률로 위로, 30% 확률로 오른쪽으로 간다는 뜻이다. 강화학습의 목표는 결국 누적 보상의 기댓값을 최대로 만드는 최적 정책 $\pi_*$ 를 찾는 것이다. 이를 위해 정책의 좋고 나쁨을 수치화할 기준이 필요하다. 그것이 다음에 나올 가치함수다. 4. 가치함수 에이전트는 현재 시점에서 앞으로 받을 보상을 고려해서 행동을 선택해야 한다. 이 “앞으로 받을 보상” 을 평가하는 개념이 바로 가치함수이다. 반환값 (Return) 에이전트가 시간 $t$로부터 행동을 하면서 받게 될 보상들을 할인해서 모두 더한 값이다. \[G_t = R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + \cdots\] 보상은 행동을 한 그 다음 타임스텝에 받으므로 $R_{t+1}$에서 시작한다는 것을 유의. 에이전트가 최대화하려는 대상은 당장의 보상 $R_{t+1}$ 이 아니라 이 반환값 이다. 또한 반환값은 “실제로 환경에서 행동하며 받은 보상의 합”이다. 반환값을 구하려면 에이전트의 행동이 유한한 시간에 끝나야 하고, 이렇게 유한한 에이전트와 환경의 상호작용을 “에피소드”라고 부른다. 환경과 정책이 확률적(불확실성을 포함)이므로 같은 상태에서 시작해도 반환값은 에피소드마다 다를 수 있다. 가치함수 (Value Function) 따라서 반환값의 기댓값을 쓴다. \[v_\pi(s) = E_\pi[G_t \mid S_t = s]\] “정책 $\pi$ 를 따를 때, 현재시점 t의 상태 $s$ 에서 앞으로 받을 것으로 기대되는 보상들의 합”이다. 큐함수 (Q-Function) 가치함수는 상태의 가치만 알려준다. 하지만 실제로 상태를 옮기려면 에이전트는 행동을 해야 하고, 행동에 따라 보상이 달라지거나 상태 변환 확률 때문에 의도한 대로 되지 않을 수도 있다. 그래서 행동을 고르려면 “현재 상태에서 각 행동을 했을 때의 가치”를 알아야 한다. 그것이 큐함수다. \[q_\pi(s, a) = E_\pi[G_t \mid S_t = s,\ A_t = a]\] 가치함수와 큐함수는 다음 관계로 이어져 있다. 상태의 가치는 그 상태에서 가능한 각 행동의 큐함수 $q_\pi(s,a)$ 를 그 행동을 할 확률 $\pi(a \mid s)$ 로 가중해서 모두 더한 것이다. 즉 정책에 따라 행동을 골랐을 때 큐함수의 기댓값이다. \[v_\pi(s) = \sum_{a \in A} \pi(a \mid s)\, q_\pi(s, a)\] 실전에서 에이전트가 행동을 선택하는 기준으로는 큐함수가 훨씬 유용하다. 가치함수만 있으면 “다음 상태의 가치”를 알기 위해 환경 모델($P_{ss’}^a$)이 필요하지만, 큐함수는 상태에서 각 행동의 가치를 직접 알려주기 때문이다. 5. 벨만 방정식 (Bellman Equation) 가치함수를 정의는 했지만, 정의대로 계산하려면 무한한 미래의 보상을 전부 합쳐야 한다. 이걸 계산 가능한 형태로 바꿔주는 것이 벨만 방정식이다. 벨만 기대 방정식 반환값은 보상들의 합이었다. 여기서 $\gamma R_{t+2}$ 부터 뒤의 항들을 $\gamma$ 로 묶어보면, 묶인 괄호 안이 다시 반환값의 형태가 된다. \[\begin{aligned} G_t &= R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + \gamma^3 R_{t+4} + \cdots \\ &= R_{t+1} + \gamma \left( R_{t+2} + \gamma R_{t+3} + \gamma^2 R_{t+4} + \cdots \right) \\ &= R_{t+1} + \gamma G_{t+1} \end{aligned}\] 즉 반환값은 “바로 다음에 받을 보상 + 할인된 다음 시점의 반환값” 으로 쪼갤 수 있다. 이를 가치함수에 그대로 대입하면 다음과 같다. \[v_\pi(s) = E_\pi[R_{t+1} + \gamma G_{t+1} \mid S_t = s]\] 그런데 $G_{t+1}$ 은 에이전트가 실제로 받은 보상이 아닌, 앞으로 받을 것이라 예상하는 값이다. 그리고 “어떤 상태에서 앞으로 받을 보상의 기댓값”은 바로 가치함수의 정의다. 따라서 $G_{t+1}$ 자리를 다음 상태의 가치함수로 바꿔 쓸 수 있다. \[v_\pi(s) = E_\pi[R_{t+1} + \gamma v_\pi(S_{t+1}) \mid S_t = s]\] 이것이 벨만 기대 방정식이다. 현재 상태의 가치함수 $v_\pi(s)$ 와 다음 상태의 가치함수 $v_\pi(S_{t+1})$ 사이의 관계를 나타낸 식으로, 미래의 보상을 전부 더하지 않고도 한 스텝 앞만 보면 가치를 계산할 수 있게 해준다. 정책과 환경을 명시적으로 풀어 쓰면 다음과 같다. \[v_\pi(s) = \sum_{a \in A} \pi(a \mid s) \left( r(s, a) + \gamma \sum_{s' \in S} P_{ss'}^a\, v_\pi(s') \right)\] 큐함수에 대해서도 같은 형태가 성립한다. \[q_\pi(s, a) = E_\pi[R_{t+1} + \gamma q_\pi(S_{t+1}, A_{t+1}) \mid S_t = s,\ A_t = a]\] 벨만 최적 방정식 벨만 기대 방정식은 “주어진 정책 $\pi$ 의 가치”를 계산한다. 하지만 우리가 원하는 건 최적 정책이다. 최적 정책이라는 것은 정책을 따라갔을 때 받을 보상들의 합인 가치함수가 가장 큰 정책이다. 이를 위해 먼저 최적 가치함수, 최적 큐함수를 정의한다. \[v_*(s) = \max_{\pi} \left[ v_\pi(s) \right], \qquad q_*(s, a) = \max_{\pi} \left[ q_\pi(s, a) \right]\] 여기서 $\max_{\pi}[\cdot]$ 는 가능한 모든 정책 $\pi$ 에 대해 대괄호 안의 값 중 최댓값을 반환하는 함수다. 즉 \(v_*(s)\) 는 어떤 정책을 쓰든 상태 $s$ 에서 얻을 수 있는 가치의 최댓값이고, \(q_*(s,a)\) 는 각 $(s,a)$ 쌍마다 모든 정책을 다 넣어 봤을 때 나오는 가장 큰 큐함수의 값이다. 이 정의에는 최적 정책 $\pi_*$ 가 등장하지 않는다는 점에 유의하자. \(v_*\) 와 \(q_*\) 는 최적 정책을 몰라도 정의되는 값이고, 최적 정책은 뒤에서 이 값들로부터 만들어진다. 최적 가치함수와 최적 큐함수의 관계 최적 큐함수 \(q_*(s,a)\) 에는 “지금 행동 $a$ 를 한 뒤, 이후 모든 시점에서도 계속 최적으로 행동한다” 는 가정이 담겨 있다. 즉 미래의 최적성이 값 안에 이미 포함되어 있으므로, 현재 상태에서는 \(q_*\)값이 가장 큰 행동 하나만 고르면 된다. 이 직관을 부등식으로 확인해 보자. (1) \(v_*(s) \le \max_a q_*(s,a)\) 임의의 정책 $\pi$ 에 대해 다음이 성립한다. \[v_\pi(s) = \sum_{a \in A} \pi(a \mid s)\, q_\pi(s,a) \;\le\; \sum_{a \in A} \pi(a \mid s)\, q_*(s,a) \;\le\; \max_{a \in A} q_*(s,a)\] 첫 번째 부등호는 \(q_*\) 의 정의에 의해 모든 정책에 대해 \(q_\pi(s,a) \le q_*(s,a)\) 이기 때문에 성립한다. 두 번째 부등호는 확률 $\pi(a \mid s)$ 로 가중합한 값이 그 최댓값을 넘을 수 없으므로 성립한다. 이 부등식은 모든 $\pi$ 에 대해 성립하므로, 좌변에 $\max_\pi$ 를 취해도 그대로 유지된다. (2) \(v_*(s) \ge \max_a q_*(s,a)\) \(a^* = \arg\max_{a} q_*(s,a)\) 라 하자. 상태 $s$ 에서 $a^*$ 를 하고, 이후에도 최적으로 행동하면 그 가치는 정확히 \(q_*(s,a^*)\) 이다. \(v_*(s)\) 는 모든 정책의 가치 중 최댓값이므로, 이 정책의 가치보다 작을 수 없다. 두 부등식을 합치면 다음 성질이 유도된다. \[v_*(s) = \max_{a \in A} q_*(s, a)\] $v_\pi(s) = \sum_a \pi(a \mid s)\, q_\pi(s,a)$ 는 행동들에 대한 가중평균이었다. 최적에서는 평균을 내는 대신 가장 좋은 행동 하나에 확률을 몰아주므로, 가중합 자리에 $\max$ 가 들어간다. 최적 정책 이제 최적 정책은 각 상태에서 최적 큐함수 \(q_*(s,a)\) 값이 가장 큰 행동을 선택하여 만들 수 있다. 즉 \(q_*\) 를 최대로 만드는 행동은 확률 1로 선택하고, 나머지 행동은 선택하지 않는다. \[\pi_*(a \mid s) = \begin{cases} 1 & \text{if } a = \arg\max_{a' \in A} \left[ q_*(s, a') \right] \\ 0 & \text{otherwise} \end{cases}\] 여기서 $\arg\max_{a’ \in A}[\cdot]$ 는 대괄호 안의 값을 최대로 만드는 행동 $a’$ 를 반환한다. \(q_*\) 의 정의에서 $\max_\pi$ 는 $(s,a)$ 쌍마다 따로 계산되므로, 원칙적으로는 상태마다 최댓값을 주는 정책이 서로 다를 수도 있다. 그러나 MDP에서는 모든 상태에서 동시에 최댓값을 달성하는 결정론적 정책이 항상 존재하며, 위처럼 \(q_*\) 에 대해 greedy하게 행동하는 정책이 바로 그것이다. 즉 “\(q_*\) 로 만든 greedy 정책을 따르면, 그 결과가 다시 \(q_*\) 를 달성한다”는 일관성이 성립한다. 주의할 점은, greedy 선택의 기준이 반드시 최적 큐함수여야 한다는 것이다. 최적이 아닌 큐함수 $q_\pi$ 는 \(q_*\) 와 달리 “현재 행동 이후에는 기존 정책 $\pi$ 를 따른다”는 가정 위에서 계산된 값이다. 따라서 $q_\pi$ 에 대해 greedy하게 행동하면 정책이 $\pi$ 보다 좋아지기는 하지만, 최적이라는 보장은 없다. 이 개선을 반복해 최적 정책에 도달하는 방법이 정책 이터레이션이다. 벨만 최적 방정식 위에서 유도한 \(v_*(s) = \max_a q_*(s,a)\) 에서 큐함수 \(q_*(s,a)\) 를 그 정의로 풀어 가치함수 형태로 고쳐 표현하면 벨만 최적 방정식이 된다. 기대 방정식에서 정책에 대한 가중합 $\sum_a \pi(a \mid s)$ 자리에 $\max_a$ 가 들어간 형태다. \[v_*(s) = \max_{a} E\left[R_{t+1} + \gamma v_*(S_{t+1}) \mid S_t = s,\ A_t = a\right]\] \[q_*(s, a) = E\left[R_{t+1} + \gamma \max_{a'} q_*(S_{t+1}, a') \mid S_t = s,\ A_t = a\right]\] 이 두 식의 우변에는 어떤 정책도 등장하지 않는다. 따라서 모든 정책을 나열해 $\max_\pi$ 를 직접 계산할 필요 없이, 이 방정식을 만족하는 \(v_*\) 또는 \(q_*\) 를 먼저 구한 뒤 greedy하게 행동하기만 하면 최적 정책을 얻을 수 있다.
Reinforcement Learning
· 2026-07-24
<
>
hemisus
